home *** CD-ROM | disk | FTP | other *** search
/ PC-X 1997 October / pcx14_9710.iso / swag / pointers.swg / 0037_Dynamically Sized List Unit.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1996-08-30  |  7.5 KB  |  210 lines
  1. unit Lists;
  2.  
  3. {--------------------------------------------------------------------------}
  4. { Abstract Data Type for dynamically sized list                            }
  5. { By Michael Dales 30th May 1996                                           }
  6. {                                                                          }
  7. { Here is a simple list unit, that has the advantage of being dynamically  }
  8. { sized, unlike normal arrays. To use the list you only need to know the   }
  9. { data type names and the methods declared in the interface of this unit   }
  10. { are used to manipulate them without the need to know the underlying      }
  11. { representation.                                                          }
  12. {                                                                          }
  13. { Deaclare your list variable to be of type TList, and remeber to use      }
  14. { CreateList on it before you carry out any operations using it. Data is   }
  15. { stored in nodes as pointers, just so you can have a list which isn't     }
  16. { tied to just one kind of data type. Remeber though that because of this  }
  17. { you'll need to typecast your pointers when you retrieve them from the    }
  18. { list. Each node is has a type called PListNode, and an invalid node has  }
  19. { the value null.                                                          }
  20. {                                                                          }
  21. { Email comments to: 9402198d@udcf.gla.ac.uk                               }
  22. { URL: http://www.gla.ac.uk/Clubs/WebSoc/~9402198d/index.html              }
  23. {--------------------------------------------------------------------------}
  24.  
  25. interface
  26.  
  27. const null = nil;        {Non specific terminator}
  28.  
  29. type PListNode = ^TListNode;             {Pointer to node}
  30.      TListNode = record                  {Node record}
  31.                Item      : Pointer;      {Pointer to node data}
  32.                Next      : PListNode;    {Next node}
  33.                Previous  : PListNode;    {Previous node}
  34.      end;
  35.  
  36.      TList = record                   {Holder for list}
  37.            First : PListNode;         {Pointer to start of list}
  38.            Rear  : PListNode;         {Pointer to end of list}
  39.            Size  : integer;           {Size of list}
  40.      end;
  41.  
  42. {CreateList - Initiates a new list}
  43. procedure CreateList(var L : TList);
  44.  
  45. {DestroyList - Frees up all memory used by list and sets list to nil}
  46. procedure DestroyList(var L : TList);
  47.  
  48. {AddNewNode - Adds new node to list L, filling it with the data
  49.               supplied. Returns true is new node sucessfully
  50.               added, otherwise returns false.}
  51. procedure AddNewNode(var L : TList; Data : Pointer);
  52.  
  53. {DeleteListElement - Deletes an element passed.}
  54. procedure DeleteNode(var L : TList; ANode : PListNode);
  55.  
  56. {GetFirstNode - Returns the first node in a given list}
  57. function GetFirstNode(L:TList):PListNode;
  58.  
  59. {GetNextNode - Returns the successor of the given node}
  60. function GetNextNode(Node:PListNode):PListNode;
  61.  
  62. {GetNodeData - Returns the data in a specific node}
  63. procedure GetNodeData(Node:PListNode; var Data:Pointer);
  64.  
  65. {UpdateNode - Replaces a nodes details with new ones}
  66. procedure UpdateNode(Node:PListNode; Data:Pointer);
  67.  
  68. {--------------------------------------------------------------------------}
  69. implementation
  70. {--------------------------------------------------------------------------}
  71.  
  72.     {CreateList - Initiates a new list}
  73.  
  74. procedure CreateList(var L : TList);
  75. begin
  76.      L.First := nil;      {No list yet}
  77.      L.Rear := nil;
  78.      L.Size := 0;         {No length yet}
  79. end;
  80.  
  81.  
  82.     {RemoveLastNode - Deletes last node on the list}
  83.  
  84. procedure RemoveLastNode(var L : TList);
  85. begin
  86.      with L do                                  {With the list}
  87.      begin
  88.           if Size > 0 then                        {If nodes in list}
  89.           begin
  90.                if Size = 1 then                   {If just one node}
  91.                begin
  92.                     if First^.Item <> nil then  {If data in node then}
  93.                        Dispose(First^.Item);        {Dispose of it}
  94.                     Dispose(First);             {Dispose of first node}
  95.                     First := nil;
  96.                     Rear := nil;                  {Set rear to nil}
  97.                end else
  98.                begin                            {If more than one node}
  99.                     Rear := Rear^.Previous;       {Set rear to second last}
  100.                     Dispose(Rear^.Next);        {Remove last node}
  101.                end;
  102.                Size := Size-1;                    {Decrement list size}
  103.           end;
  104.      end;
  105. end;
  106.  
  107.  
  108.     {DestroyList - Frees up all memory used by list and sets list to nil}
  109.  
  110. procedure DestroyList(var L : TList);
  111. begin
  112.      while L.First <> nil do              {While still nodes left}
  113.            RemoveLastNode(L);             {Remove last node}
  114.      CreateList(L);
  115. end;
  116.  
  117.  
  118.     {GetFirstNode - Returns the first node in a given list}
  119.  
  120. function GetFirstNode(L : TList) : PListNode;
  121. begin
  122.      GetFirstNode := L.First;
  123. end;
  124.  
  125.  
  126.     {GetNextNode - Returns the successor of the given node}
  127.  
  128. function GetNextNode(Node : PListNode) : PListNode;
  129. begin
  130.      if Node <> nil then
  131.         GetNextNode := Node^.Next
  132.      else
  133.          GetNextNode := nil;
  134. end;
  135.  
  136.  
  137.     {GetNodeData - Returns the data in a specific node}
  138.  
  139. procedure GetNodeData(Node : PListNode; var Data : Pointer);
  140. begin
  141.      if Node <> nil then
  142.         Data := Node^.Item
  143.      else
  144.          Data := nil;
  145. end;
  146.  
  147.  
  148.     {AddNewNode - Adds new node to list L, filling it with the data
  149.                   supplied. Returns true is new node sucessfully
  150.                   added, otherwise returns false.}
  151.  
  152. procedure AddNewNode(var L:TList; Data:Pointer);
  153. var temp    : PListNode;
  154. begin
  155.      new(temp);                 {Create new node}
  156.      with temp^ do              {Fill node}
  157.      begin
  158.           Item := Data;
  159.           Next := nil;
  160.           Previous := L.Rear;
  161.      end;
  162.      If (L.Size = 0) then         {If empty list...}
  163.      begin
  164.           L.First := temp;        {Add as first node}
  165.           L.Rear := temp;
  166.      end else                       {else add at end}
  167.      begin
  168.           L.Rear^.Next := temp;  {Make old rear of list point to new}
  169.           L.Rear := temp;        {Make rear point to new node}
  170.      end;
  171.      L.Size := L.Size + 1;          {Increment list length}
  172. end;
  173.  
  174.  
  175.     {UpdateNode - Replaces a nodes details with new ones}
  176.  
  177. procedure UpdateNode(Node : PListNode; Data : Pointer);
  178. begin
  179.      if Node <> nil then
  180.      begin
  181.           Node^.Item := Data;
  182.      end;
  183. end;
  184.  
  185.  
  186.     {DeleteListElement - Deletes an element passed.}
  187.  
  188. procedure DeleteNode(var L : TList; ANode : PListNode);
  189. begin
  190.      if (L.Size = 1) or (ANode^.Next = nil) then    {If we're deeling with}
  191.         RemoveLastNode(L)            {last node then that's easy}
  192.      else                            {otherwise...}
  193.      begin
  194.           if (ANode = L.First) then      {if we're deleting the first node}
  195.           begin
  196.                L.First := L.First^.Next;    {Start list from second node}
  197.                L.First^.Previous := nil;    {Set new starts previous link}
  198.                Dispose(ANode);              {Dispose of old first}
  199.           end else
  200.           begin
  201.                ANode^.Previous^.Next := ANode^.next;     {Move pointers...}
  202.                ANode^.Next^.Previous := ANode^.Previous;
  203.                Dispose(ANode);          {Dispose of node}
  204.           end;
  205.           L.Size := L.Size-1;           {Note new list size}
  206.      end;
  207. end;
  208.  
  209. end.
  210.